package lib

import (
	"algorithms/ds"
)

func init() {
	Probs = append(Probs, Problem{
		Num:         142,
		Discription: "返回链表入环位置",
		Level:       2,
		Labels: map[string]int{
			"链表":   1,
			"快慢指针": 1,
		},
	})
}

// 设直线区域长度为a，环的长度为a+b
// fast和slow在a相遇
// 由于fast走的步数是slow的两倍：c+n(a+b)+a = 2(c+a),得c = (n-1)a+nb
// 再让temp指向head，和slow一起再走c步，slow的步数为：c+a+c = c+a+(n-1)a+nb = c+n(a+b)，与temp重合，此时的位置就是入环点
func DetectCycle(head *ds.ListNode) *ds.ListNode {
	if head == nil {
		return nil
	}

	//必须两个都从head开始
	fast := head
	slow := head
	for {
		if fast == nil || fast.Next == nil {
			return nil
		}

		fast = fast.Next.Next
		slow = slow.Next
		if fast == slow {
			break
		}
	}

	temp := head
	for temp != slow {
		temp = temp.Next
		slow = slow.Next
	}

	return temp
}
